/**
 * @author LKQ
 * @date 2022/1/20 17:37
 * @description
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2  solution2 = new Solution2();
        solution2.longestPalindrome("babad");
    }
    public String longestPalindrome(String s) {
        char[] str = s.toCharArray() ;
        int[] rage = new int[2] ;
        int n = s.length() ;
        for(int i=0 ; i<n ; i++){
            // 把回文看成中间部分全是同一个字符，左右部分对称
            i = findlongest(str , i , rage) ;
        }
        return s.substring(rage[0] , rage[1]+1) ;
    }

    public static int findlongest(char[] str , int low , int[] rage){
        // 查找中间部分
        int high = low ;
        while(high<str.length-1 && str[high+1] == str[low]){
            high++ ;
        }
        // 定位中间部分的最后一个字符
        int ans = high ;
        // 从中间位置从左右扩散
        while(low>0 && high<str.length-1 && str[high+1]==str[low-1]){
            high++ ;
            low-- ;
        }
        // 记录最大长度
        if(high-low > rage[1] - rage[0]){
            rage[1] = high ;
            rage[0] = low  ;
        }
        return ans ;
    }
}
